package Year22_Month06.day24;

public class 二叉搜索树中的插入操作_迭代写法 {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null) return new TreeNode(val);
        //定义两个节点指针，用来进行当前节点和上一个节点的保存
        TreeNode parent = root,key = root;
        while(key != null){
            parent = key;
            key = key.val < val ? key.right : key.left;
        }
        //注意哈，这里如果说插入节点的值等于当前节点的话，会把当前节点的值进行覆盖
        if(parent.val > val) parent.left = new TreeNode(val);
        else if(parent.val < val)  parent.right = new TreeNode(val);
        return root;
    }
}
